package src.linkeLlist;

public class no143 {  //重排链表，2019年408算法题

    //1、链表从中间拆分
    //2、后半段逆置
    //3、交叉合并
    public void reorderList(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode head2 = slow.next;
        slow.next = null;

        //断开后一定前半段 >= 后半段
        ListNode q = no206.reverseList(head2);  //这里直接逆置，也可定义虚拟头结点，采用头插法
        ListNode p = head;
        while (q != null) {
            ListNode r = p.next, s = q.next;
            p.next = q;
            q.next = r;
            p = r;
            q = s;
        }
    }
}
